{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Subarrays with Bounded Maximum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSubarrayBoundedMax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #区间子数组个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和两个整数：<code>left</code> 及 <code>right</code> 。找出 <code>nums</code> 中连续、非空且其中最大元素在范围&nbsp;<code>[left, right]</code> 内的子数组，并返回满足条件的子数组的个数。</p>\n",
    "\n",
    "<p>生成的测试用例保证结果符合 <strong>32-bit</strong> 整数范围。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,1,4,3], left = 2, right = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>满足条件的三个子数组：[2], [2, 1], [3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,9,2,5,6], left = 2, right = 8\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= left &lt;= right &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-subarrays-with-bounded-maximum](https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-subarrays-with-bounded-maximum](https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4,3]\\n2\\n3', '[2,9,2,5,6]\\n2\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        last2 = last1 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if left <= x <= right:\n",
    "                last1 = i\n",
    "            elif x > right:\n",
    "                last2 = i\n",
    "                last1 = -1\n",
    "            if last1 != -1:\n",
    "                res += last1 - last2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], a: int, b: int) -> int:\n",
    "        n,ans=len(nums),0\n",
    "        j,k=-1,-1\n",
    "        for i in range(n):\n",
    "            if nums[i]>b:\n",
    "                k=i\n",
    "            else:\n",
    "                if nums[i]<a:\n",
    "                    ans+=j-k if j>k else 0\n",
    "                else:\n",
    "                    ans+=i-k\n",
    "                    j=i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans,slow,fast = 0,-1,-1\n",
    "        for idx,i in enumerate(nums):\n",
    "            if i > right:\n",
    "                slow = idx\n",
    "            if i >= left:\n",
    "                fast = idx\n",
    "            ans += fast -slow\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        last2 = last1 = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if left <= x <= right:\n",
    "                last1 = i\n",
    "            elif x > right:\n",
    "                last2 = i\n",
    "                last1 = -1\n",
    "            if last1 != -1:\n",
    "                res += last1 - last2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        j, temp, ans = -1, 0, 0\n",
    "        for i in range(n):\n",
    "            if nums[i] > right:\n",
    "                j = i\n",
    "            if nums[i] >= left:\n",
    "                temp = i - j\n",
    "\n",
    "            ans += temp\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        last1 = -1\n",
    "        last2 = -1\n",
    "        for i in range(len(nums)):\n",
    "            if left <= nums[i] and nums[i] <= right:\n",
    "                last1 = i\n",
    "            elif nums[i] > right:\n",
    "                last1 = -1\n",
    "                last2 = i # last invalid\n",
    "            if last1 != -1:\n",
    "                ans += last1 - last2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        end_index = start_index = -1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > right:\n",
    "                end_index = start_index = i\n",
    "            else:\n",
    "                if left <= nums[i] <= right:\n",
    "                    end_index = i\n",
    "                ans += (end_index - start_index)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def calculate(nums, k):\n",
    "            i = j = ret = 0\n",
    "            n = len(nums)\n",
    "            while i < n:\n",
    "                if nums[i] > k:\n",
    "                    j = i + 1\n",
    "                ret += i - j + 1\n",
    "                i += 1\n",
    "            return ret\n",
    "        return calculate(nums, right) - calculate(nums, left - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        last1, last2, ans = -1, -1, 0\n",
    "        for i in range(len(nums)):\n",
    "            if left <= nums[i] <= right:\n",
    "                last2 = i\n",
    "            elif nums[i] > right:\n",
    "                last1 = i\n",
    "                last2 = -1\n",
    "            if last2 != -1:\n",
    "                ans += last2 - last1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans, i0, i1 = 0, -1, -1\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > right: i0 = i\n",
    "            if x >= left: i1 = i\n",
    "            ans += i1 - i0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans,i0,i1=0,-1,-1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x>right:i0=i\n",
    "            if x>=left:i1=i\n",
    "            ans+=i1-i0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ret = 0\n",
    "        last1 = last2 = -1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < left:\n",
    "                if last1 > last2:\n",
    "                    ret += last1 - last2\n",
    "            elif nums[i] > right:\n",
    "                last2 = i\n",
    "            else:\n",
    "                last1 = i\n",
    "                ret += last1 - last2\n",
    "            if ret < 0:\n",
    "                print(\"debug\")\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        i,j,k = 0,0,0\n",
    "        while j < n:\n",
    "            if nums[j] < left:\n",
    "                dp[j] += dp[k]\n",
    "            elif nums[j] > right:\n",
    "                i = j+1\n",
    "                k = j+1\n",
    "            else:\n",
    "                dp[j] = j-i+1\n",
    "                k = j\n",
    "            j += 1\n",
    "        return sum(dp)\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(t):\n",
    "    res = 0\n",
    "\n",
    "def func(x, left, right):\n",
    "    res = 0\n",
    "    n = len(x)\n",
    "    for i in range(n):\n",
    "        if x[i] < left:\n",
    "            if i + 1 != n:\n",
    "                for j in range(i+1,n):\n",
    "                    if x[j] >= left:\n",
    "                        res += n -j\n",
    "                        break\n",
    "        else:\n",
    "            res += n - i\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        maxNumber = left - 1\n",
    "        while j < n:\n",
    "            if nums[j] >= left and nums[j] <= right:\n",
    "                maxNumber = max(maxNumber, nums[j])\n",
    "                j += 1\n",
    "            elif maxNumber >= nums[j]:\n",
    "                j += 1\n",
    "            else:\n",
    "                if i != j:\n",
    "                    res.append(nums[i:j])\n",
    "                j += 1\n",
    "                i = j\n",
    "                maxNumber = left - 1\n",
    "        if i != j:\n",
    "            res.append(nums[i:j])\n",
    "        a = 0\n",
    "        print(res)\n",
    "        for i in res:\n",
    "            a += func(i, left, right)\n",
    "        return a            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] *n\n",
    "        if left <= nums[0] and nums[0] <= right:\n",
    "            dp[0] = 1\n",
    "        for i in range(1,n):\n",
    "            if nums[i] >= left and nums[i] <= right:                \n",
    "                x = 0\n",
    "                j = i - 1\n",
    "                while j >= 0 and nums[j] < left:                    \n",
    "                        x += 1\n",
    "                        j -= 1\n",
    "                dp[i] = dp[i-1] + 1 + x\n",
    "            elif nums[i] < left:\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    #print(i, j, nums[j])\n",
    "                    if nums[j] >= left:\n",
    "                        dp[i] = dp[j]\n",
    "                        break\n",
    "        #print(dp)\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        temp = 0\n",
    "        if left <= nums[0] <= right:\n",
    "            dp[0] = 1\n",
    "        if nums[0] < left:\n",
    "            temp = 1\n",
    "        if n <= 1:\n",
    "            return dp[0] \n",
    "        for i in range(1,n):\n",
    "            if nums[i] < left:\n",
    "                dp[i] = dp[i-1]\n",
    "                temp += 1\n",
    "            elif nums[i] > right:\n",
    "                dp[i] = 0\n",
    "                temp = 0\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + temp + 1\n",
    "                temp = 0\n",
    "        return sum(dp)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] <= v:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        return sum((i - l[i]) * (r[i] - i) for i, v in enumerate(nums) if left <= v <= right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], l: int, r: int) -> int:\n",
    "        n=len(nums)\n",
    "        left,right=[-1]*n,[n]*n\n",
    "        q=deque()\n",
    "        for i in range(n):\n",
    "            while q and nums[q[-1]]<=nums[i]:\n",
    "                q.pop()\n",
    "            if q:\n",
    "                left[i]=q[-1]\n",
    "            q.append(i)\n",
    "        q=deque()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while q and nums[q[-1]]<nums[i]:\n",
    "                q.pop()\n",
    "            if q:\n",
    "                right[i]=q[-1]\n",
    "            q.append(i)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if l<=nums[i]<=r:\n",
    "                ans+=(i-left[i])*(right[i]-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        d=[]\n",
    "        c=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>right:\n",
    "                d.append(i)\n",
    "            if nums[i]>=left:\n",
    "                c.append(i)\n",
    "        s=0\n",
    "        def j(a):\n",
    "            return a*(a+1)/2\n",
    "        if d==[]:\n",
    "            s+=j(len(nums))\n",
    "        else:\n",
    "            s+=j(d[0])\n",
    "            for i in range(1,len(d)):\n",
    "                s+=j(d[i]-d[i-1]-1)\n",
    "            s+=j(len(nums)-1-d[-1])\n",
    "        if c==[]:\n",
    "            return int(s)\n",
    "        else:\n",
    "            s-=j(c[0])\n",
    "            for i in range(1,len(c)):\n",
    "                s-=j(c[i]-c[i-1]-1)\n",
    "            s-=j(len(nums)-1-c[-1])\n",
    "            return int(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n, res = len(nums), 0\n",
    "        l, r = [-1]*n, [n]*n\n",
    "\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]]<=nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        \n",
    "        stk = []\n",
    "        for i in range(n)[::-1]:\n",
    "            while stk and nums[stk[-1]]<nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i]>=left and nums[i]<=right:\n",
    "                res = res + (i-l[i])*(r[i]-i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        单调栈做法, 单调栈枚举所有子区间最值为nums[i]的子区间\n",
    "\n",
    "        统计所有最大值范围在 [a, b] 之间的子数组个数，可等价为统计每一个范围落在 [a, b] 之间的 nums[i] 作为最大值时子数组的个数。\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "\n",
    "        # 取[lower_i, upper_i]\n",
    "        upper = [n] * n\n",
    "        lower = [-1] * n\n",
    "\n",
    "        # 单调栈统计每个元素为最大值的最大区间长度\n",
    "        st = []\n",
    "        for i, num in enumerate(nums):\n",
    "            while st and num >= nums[st[-1]]:\n",
    "                upper[st[-1]] = i\n",
    "                st.pop()\n",
    "            # //** 此处统计左侧第一个大于nums[i]的元素  **//\n",
    "            lower[i] = st[-1] if st else -1\n",
    "            st.append(i)\n",
    "\n",
    "        # 枚举最大值为 nums[i] 的所有区间\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += (upper[i] - i) * (i - lower[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        \"\"\"\n",
    "        使用单调栈, 统计左侧第一个大于当前元素, 和右侧第一个大于等于当前元素\n",
    "\n",
    "        单调栈统计左侧第一个大于当前元素: while循环退出后的栈顶即是左侧第一个大于当前元素的位置\n",
    "            统计右侧第一个大于当前元素可以在while循环内部出栈的时候, 当前元素的位置 是 出栈元素右侧第一个大于的位置\n",
    "\n",
    "        或者采用倒序遍历的思路, 此时while循环退出时的栈顶元素即是 当前元素右侧第一个大于的位置\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[i] >= nums[st[-1]]:\n",
    "                # r[st[-1]] = i\n",
    "                st.pop()\n",
    "            # nums[l[i]] > nums[i]\n",
    "            l[i] = st[-1] if st else -1\n",
    "            st.append(i)\n",
    "\n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[i] > nums[st[-1]]:\n",
    "                st.pop()\n",
    "            # nums[r[i]] >= nums[i]\n",
    "            r[i] = st[-1] if st else n\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += (i - l[i]) * (r[i] - i)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        # last2=last1=-1\n",
    "        # ans=0\n",
    "        # for i in range(len(nums)):\n",
    "        #     if left<=nums[i]<=right:\n",
    "        #         last1=i\n",
    "        #     elif nums[i]>right:\n",
    "        #         last2=i\n",
    "        #     ans+=max(0,last1-last2)\n",
    "        # return ans\n",
    "\n",
    "        stack=[]\n",
    "        n=len(nums)\n",
    "        lm,rm=[-1]*n,[n]*n\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]]<=nums[i]:\n",
    "                cur=stack.pop()\n",
    "                rm[cur]=i\n",
    "            stack.append(i)\n",
    "        stack=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and nums[stack[-1]]<nums[i]:\n",
    "                cur=stack.pop()\n",
    "                lm[cur]=i\n",
    "            stack.append(i)\n",
    "        return sum((i-lm[i])*(rm[i]-i) for i in range(n) if left<=nums[i]<=right)\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] <= nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += (i - l[i]) * (r[i] - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "方法二：单调栈 + 枚举元素计算贡献\n",
    "\n",
    "我们还可以枚举数组中每个元素 nums[i] 作为子数组的最大值，然后统计以该元素为最大值的子数组的个数。\n",
    "问题转化为求出每个元素 nums[i] 左侧第一个大于该元素的下标 l[i]l[i]，右侧第一个大于等于该元素的下标 r[i]r[i]，\n",
    "则以该元素为最大值的子数组的个数为 (i−l[i])×(r[i]−i)。\n",
    "\n",
    "我们可以使用单调栈方便地求出 l[i]l[i] 和 r[i]r[i]\n",
    "\n",
    "时间复杂度 O(n)，空间复杂度 O(n)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] <= v:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        return sum((i - l[i]) * (r[i] - i) for i, v in enumerate(nums) if left <= v <= right)\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "方法一：区间计数\n",
    "\n",
    "题目要我们统计数组 nums 中，最大值在区间 [left,right] 范围内的子数组个数。\n",
    "对于区间 [left,..right] 问题，我们可以考虑将其转换为 [0,..right] 然后再减去 [0,..left−1] 的问题。\n",
    "也就是说，所有最大元素不超过 right 的子数组个数，减去所有最大元素不超过 left−1 的子数组个数，剩下的就是最大元素在区间 [left,..right] 范围内的子数组个数。\n",
    "\n",
    "对于本题，我们只需要设计一个函数 f(x)，表示数组 nums 中，最大值不超过 x 的子数组个数。\n",
    "那么答案为 f(right)−f(left−1)。函数 f(x) 的执行逻辑如下：\n",
    "1)用变量 cnt 记录最大值不超过 x 的子数组的个数，用 t 记录当前子数组的长度。\n",
    "2)遍历数组 nums，对于每个元素 nums[i]，如果 nums[i]≤x，则当前子数组的长度加一，即 t=t+1，\n",
    "否则当前子数组的长度重置为 0，即 t=0。然后将当前子数组的长度加到 cnt 中，即cnt=cnt+t。\n",
    "3)遍历结束，将 cnt 返回即可。\n",
    "\n",
    "时间复杂度 O(n)，空间复杂度 O(1)\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def f(x):\n",
    "            cnt = t = 0\n",
    "            for v in nums:\n",
    "                t = 0 if v > x else t + 1\n",
    "                cnt += t\n",
    "            return cnt\n",
    "\n",
    "        return f(right) - f(left - 1)\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n      #以i为终点的符合题目要求的个数\n",
    "        dp1 = [0] * n     #以i为终点的小于right的个数\n",
    "        ans = 0\n",
    "\n",
    "        if nums[0] <= right:\n",
    "            dp1[0] = 1\n",
    "            if nums[0] >= left:\n",
    "                dp[0] = 1\n",
    "                ans = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if left <= nums[i] <= right:\n",
    "                dp[i] = dp1[i-1] + 1\n",
    "                dp1[i] = dp1[i-1] + 1\n",
    "            elif nums[i] < left:\n",
    "                dp[i] = dp[i-1]\n",
    "                dp1[i] = dp1[i-1] + 1\n",
    "\n",
    "            ans += dp[i]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], l: int, r: int) -> int:\n",
    "        N = len(nums)\n",
    "        left = [-1] * N  # left[i] 为左侧严格大于 nums[i] 的最近元素位置（不存在时为-1）\n",
    "        right = [N] * N  # left[i] 为右侧大于等于 nums[i] 的最近元素位置（不存在时为 N）\n",
    "        st = []\n",
    "        for i, n in enumerate(nums):\n",
    "            while st and nums[st[-1]] <= n:\n",
    "                popi = st.pop()\n",
    "                right[popi] = i\n",
    "            left[i] = st[-1] if st else -1\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            if l <= n <= r:\n",
    "                print(left[i], i, right[i], n, (i - left[i]) * (right[i] - i))\n",
    "                ans += (i - left[i]) * (right[i] - i)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        #贡献法，用单调递减栈求出在[a,b]区间内nums[i]最大值时的左右边界\n",
    "        n, res = len(nums), 0\n",
    "        left_idx, right_idx = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                right_idx[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stk and nums[stk[-1]] <= nums[i]:\n",
    "                left_idx[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                res += (right_idx[i] - i) * (i - left_idx[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, A, L, R):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type L: int\n",
    "        :type R: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left = 0\n",
    "        result = []\n",
    "        tmp = 0\n",
    "        \n",
    "        for i, c in enumerate(A):\n",
    "            if c > R:\n",
    "                # 大于 R 的数，分隔 A 为一个个小区间\n",
    "                tmp = 0\n",
    "                left = i + 1\n",
    "            elif c >= L:\n",
    "                # 在小区间内，从左到右，遇到 L <= c <= R，组合数会增加 i - left + 1\n",
    "                tmp = i - left + 1\n",
    "                result.append(tmp)\n",
    "            else:\n",
    "                # 在小区间内，从左到右，遇到 c < L，组合数会增加之前那么多种\n",
    "                result.append(tmp)\n",
    "        return sum(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        stack = []\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] < num:\n",
    "                j = stack.pop()\n",
    "                r[j] = i\n",
    "            if stack:\n",
    "                l[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            if left <= num <= right:\n",
    "                ans += (i - l[i]) * (r[i] - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        lastAlp = [0] * len(nums)\n",
    "        smallThanLeft = 0\n",
    "        if left <= nums[0] <= right:\n",
    "            lastAlp[0] = 1\n",
    "        elif nums[0] < left:\n",
    "            smallThanLeft += 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < left:\n",
    "                smallThanLeft += 1\n",
    "                lastAlp[i] = lastAlp[i - 1]\n",
    "            elif left <= nums[i] <= right:\n",
    "                lastAlp[i] = lastAlp[i - 1] + smallThanLeft + 1\n",
    "                smallThanLeft = 0\n",
    "            else:\n",
    "                smallThanLeft = 0\n",
    "        return sum(lastAlp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def linearsearch(target, l):\n",
    "            for mid in range(l, len(nums)):\n",
    "                if nums[mid] < target:\n",
    "                    return mid\n",
    "        l = 0\n",
    "        cnt = 0\n",
    "        Dict = {}\n",
    "        sta = deque() # 保存最大值，单调递减栈\n",
    "        for r in range(len(nums)): # [l, r]闭区间\n",
    "            while sta and nums[sta[-1]] < nums[r]:\n",
    "                sta.pop()\n",
    "            sta.append(r)\n",
    "            # 不可行窗口可行化\n",
    "            while l <= r and sta and nums[sta[0]] > right:\n",
    "                l = sta.popleft() + 1\n",
    "            if l <= r and sta and nums[sta[0]] >= left:\n",
    "                # mid = binarysearch(sta, left)\n",
    "                if nums[sta[-1]] >= left:\n",
    "                    Dict[l] = r + 1\n",
    "                    cnt += r - l + 1\n",
    "                else:\n",
    "                    if l not in Dict:\n",
    "                        Dict[l] = linearsearch(left, l)\n",
    "                    cnt += Dict[l] - l\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp =[0 for _ in range(n)]\n",
    "        smaller = 0\n",
    "        for i in range(0, n):\n",
    "            if nums[i] > right:\n",
    "                dp[i] = 0\n",
    "                smaller = 0\n",
    "            elif nums[i] >= left:\n",
    "                dp[i] = smaller + 1\n",
    "                smaller += 1\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "                smaller += 1\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        smallerCount = [0 for _ in range(len(nums))]\n",
    "        cnt = 0\n",
    "        smaller = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] <= right and nums[i] >= left:\n",
    "                cnt += 1 + smaller\n",
    "                smaller = 0\n",
    "            elif nums[i] < left:\n",
    "                smaller += 1\n",
    "            else:\n",
    "                cnt = 0\n",
    "                smaller = 0\n",
    "            smallerCount[i] = cnt\n",
    "\n",
    "        return sum(smallerCount)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        i_over=-1\n",
    "        dp=[]\n",
    "        if nums[0]>right:\n",
    "            dp.append(0)\n",
    "            i_over=0\n",
    "        elif nums[0]>=left:\n",
    "            dp.append(1)\n",
    "        else:\n",
    "            dp.append(0)\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>right:\n",
    "                dp.append(0)\n",
    "                i_over = i\n",
    "            elif nums[i]>=left:\n",
    "                dp.append(i-i_over)\n",
    "            else:\n",
    "                dp.append(dp[i-1])\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def cal(sub_nums):\n",
    "            record = [0] * len(sub_nums)\n",
    "            if len(sub_nums) == 0:\n",
    "                return 0\n",
    "            record[0] = 1 if left <= sub_nums[0] <= right else 0\n",
    "            for j in range(1, len(sub_nums)):\n",
    "                if left <= sub_nums[j] <= right:\n",
    "                    record[j] = j + 1\n",
    "                else:\n",
    "                    record[j] = record[j - 1]\n",
    "            return sum(record)\n",
    "\n",
    "        i = 0\n",
    "        while nums[i] > right and i < len(nums):\n",
    "            i += 1\n",
    "        last = i\n",
    "        res = 0\n",
    "        for i in range(i, len(nums)):\n",
    "            if nums[i] > right:\n",
    "                res += cal(nums[last:i])\n",
    "                last = i + 1\n",
    "        if nums[-1] <= right:\n",
    "            res += cal(nums[last:i + 1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], a: int, b: int) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        l, r = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                r[stk.pop()] = i\n",
    "            if stk:\n",
    "                l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            if a <= nums[i] <= b:\n",
    "                ans += (i - l[i]) * (r[i] - i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        if left <= nums[0] <= right:\n",
    "            dp[0] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < left:\n",
    "                dp[i] = dp[i - 1]\n",
    "            elif nums[i] > right:\n",
    "                dp[i] = 0\n",
    "            else:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "                temp = i - 1\n",
    "                while temp >= 0 and nums[temp] < left:\n",
    "                    dp[i] += 1\n",
    "                    temp -= 1\n",
    "        return sum(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=[1]*n\n",
    "        ans[0]=1 if nums[0] >= left and nums[0] <= right else 0\n",
    "        f=0 if nums[0]>right else -1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<left:\n",
    "                ans[i]=0\n",
    "                ans[i]+=ans[i-1]\n",
    "                \n",
    "   \n",
    "            elif nums[i]>right:\n",
    "                ans[i]=0\n",
    "                f=i\n",
    "            else:\n",
    "                \n",
    "                ans[i]=(i-f)\n",
    "                \n",
    "      \n",
    "        for i,j in zip(ans,nums):\n",
    "            print(i,j)     \n",
    "        return sum(ans)                \n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        dp = [0]*len(nums)\n",
    "        if left <= nums[0] <= right:\n",
    "            dp[0] = 1\n",
    "        res = dp[0]\n",
    "        max_0 = -1\n",
    "        if nums[0] > right:\n",
    "            max_0 = 0 \n",
    "        for i in range(1,len(dp)):\n",
    "            if nums[i] > right:\n",
    "                max_0 = i \n",
    "                continue \n",
    "            else:\n",
    "                if left <= nums[i] <= right:\n",
    "                    # 只要不碰壁就能一直选\n",
    "                    dp[i] = i - max_0\n",
    "                else:\n",
    "                    dp[i] = dp[i-1]\n",
    "            res += dp[i]\n",
    "        # print(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 定义两个数组，分别保存左边的第一个最大值和右边的第一个最大值的索引\n",
    "        # 注意初始化的时候，应该分别保存最左边和最右边两个值\n",
    "        l,r = [0]*n, [0]*n\n",
    "\n",
    "        # 定义单调栈（单调递减）\n",
    "        stk = []\n",
    "        # 注意当有重复元素时，可能会导致重复子数组\n",
    "        # 所有单调栈时，左闭右开或者左开右闭\n",
    "        for idx, num in enumerate(nums):\n",
    "\n",
    "            while stk and num >= nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                l[idx] = stk[-1]\n",
    "            # 可以不用写，在初始化的时候解决就可以了这里写是因为为了逻辑清晰\n",
    "            else:\n",
    "                l[idx] = -1\n",
    "            stk.append(idx)\n",
    "\n",
    "        stk = []\n",
    "        for idx in range(n-1,-1,-1):\n",
    "            num = nums[idx]\n",
    "            # 左边界的时候，是>=,这里选择>, 避免重复\n",
    "            while stk and num > nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                r[idx] = stk[-1]\n",
    "            else:\n",
    "                r[idx] = n\n",
    "            stk.append(idx)\n",
    "        print(l,r)\n",
    "        res = 0\n",
    "        for idx in range(n):\n",
    "            if left <= nums[idx] <= right:\n",
    "                res += (idx-l[idx])*(r[idx]-idx)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        cnt = 0\n",
    "        dp = len(nums) * [None]\n",
    "        debit=0\n",
    "        for i,num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                if num <= right and num>=left:\n",
    "                    dp[0] = 1\n",
    "                else:\n",
    "                    dp[0]=0\n",
    "                if num < left:\n",
    "                    debit+=1\n",
    "                continue\n",
    "            cnt += dp[i-1]\n",
    "            if num > right:\n",
    "                dp[i] = 0\n",
    "                debit=0\n",
    "            elif num < left:\n",
    "                dp[i] = dp[i-1] \n",
    "                debit += 1\n",
    "            else:\n",
    "                dp[i] = dp[i-1]  + 1\n",
    "                j = i\n",
    "                if nums[j-1] < left:\n",
    "                    print(debit)\n",
    "                    dp[i] += debit\n",
    "                    debit=0\n",
    "                    \n",
    "        print(dp)\n",
    "        return  cnt+dp[-1]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        cnt = 0\n",
    "        dp = len(nums) * [None]\n",
    "        for i,num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                if num <= right and num>=left:\n",
    "                    dp[0] = 1\n",
    "                else:\n",
    "                    dp[0]=0\n",
    "                continue\n",
    "            if num > right:\n",
    "                dp[i] = 0\n",
    "                cnt = dp[i-1] + cnt\n",
    "            elif num < left:\n",
    "                dp[i] = dp[i-1] \n",
    "            else:\n",
    "                dp[i] = dp[i-1]  + 1\n",
    "                j = i\n",
    "                while nums[j-1] < left and (j-1)>=0:\n",
    "                    dp[i] += 1\n",
    "                    j = j-1\n",
    "                \n",
    "                    \n",
    "        \n",
    "        print(dp)\n",
    "        return  sum(dp)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        mono_st = []\n",
    "        mono_st_pos = []\n",
    "\n",
    "        def binSearchRight(arr, start, end, right, res):\n",
    "            if start > end:\n",
    "                return\n",
    "            \n",
    "            mid = (start + end) // 2\n",
    "            if arr[mid] > right:\n",
    "                binSearchRight(arr, mid + 1, end, right, res)\n",
    "            else:\n",
    "                res[0] = mid\n",
    "                binSearchRight(arr, start, mid - 1, right, res)\n",
    "                \n",
    "        \n",
    "        def binSearchLeft(arr, start, end, left, res):\n",
    "            if start > end:\n",
    "                return\n",
    "            \n",
    "            mid = (start + end) // 2\n",
    "            if arr[mid] < left:\n",
    "                binSearchLeft(arr, start, mid - 1, left, res)\n",
    "            else:\n",
    "                res[0] = mid\n",
    "                binSearchLeft(arr, mid + 1, end, left, res)\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            num = nums[i]\n",
    "\n",
    "            while mono_st and mono_st[-1] < num:\n",
    "                mono_st.pop()\n",
    "                mono_st_pos.pop()\n",
    "\n",
    "            mono_st.append(num)\n",
    "            mono_st_pos.append(i)\n",
    "\n",
    "            if num > right:\n",
    "                continue\n",
    "            elif num < left:\n",
    "                y = [-1]\n",
    "                binSearchRight(mono_st, 0, len(mono_st) - 1, right, y)\n",
    "                x = [-1]\n",
    "                binSearchLeft(mono_st, 0, len(mono_st) - 1, left, x)\n",
    "\n",
    "                if x[0] == -1 or y[0] == -1 or x[0] < y[0]:\n",
    "                    continue\n",
    "                \n",
    "                A = mono_st_pos[y[0] - 1] + 1 if y[0] >= 1 else 0\n",
    "                B = mono_st_pos[x[0]]\n",
    "                res += (B - A + 1)\n",
    "            else:\n",
    "                y = [-1]\n",
    "                binSearchRight(mono_st, 0, len(mono_st) - 1, right, y)\n",
    "                B = i\n",
    "                A = mono_st_pos[y[0] - 1] + 1 if y[0] >= 1 else 0\n",
    "                res += (B - A + 1)\n",
    "        \n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        cnt = 0\n",
    "        dp = len(nums) * [None]\n",
    "        for i,num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                if num <= right and num>=left:\n",
    "                    dp[0] = 1\n",
    "                else:\n",
    "                    dp[0]=0\n",
    "                continue\n",
    "            if num > right:\n",
    "                dp[i] = 0\n",
    "                cnt = dp[i-1] + cnt\n",
    "            elif num < left:\n",
    "                dp[i] = dp[i-1] \n",
    "            else:\n",
    "                dp[i] = dp[i-1]  + 1\n",
    "                j = i\n",
    "                while nums[j-1] < left and (j-1)>=0:\n",
    "                    dp[i] += 1\n",
    "                    j = j-1\n",
    "                \n",
    "                    \n",
    "        \n",
    "        print(dp)\n",
    "        return  sum(dp)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        ans = 0\n",
    "        stk = []\n",
    "        arr = [inf] + nums + [inf]\n",
    "        for i, x in enumerate(arr):\n",
    "            while stk and x > arr[stk[-1]]:\n",
    "                r = i - stk[-1]\n",
    "                l = stk[-1] - stk[-2]\n",
    "                if left <= arr[stk[-1]] <= right:\n",
    "                    ans += l * r\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        nums = [float('inf')] + nums + [float('inf')]\n",
    "        for i, x in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] < x:\n",
    "                idx = stack.pop()\n",
    "                if nums[idx] >= left and nums[idx] <= right:\n",
    "                    peak = stack[-1]\n",
    "                    res += (i-idx) * (idx-peak)\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        p1 = [None] * n\n",
    "        p2 = [None] * n\n",
    "\n",
    "        if left <= nums[n-1] <= right:\n",
    "            p1[n-1] = n-1\n",
    "        if nums[n-1] > right:\n",
    "            p2[n-1] = n-1\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            p1[i] = p1[i+1]\n",
    "            p2[i] = p2[i+1]\n",
    "\n",
    "            if left <= nums[i] <= right:\n",
    "                p1[i] = i\n",
    "            if nums[i] > right:\n",
    "                p2[i] = i\n",
    "\n",
    "        print(p1, p2)\n",
    "\n",
    "        tot = 0\n",
    "        for i in range(n):\n",
    "            a, b = p1[i], p2[i]\n",
    "            if a is None:\n",
    "                continue\n",
    "\n",
    "            if b is None:\n",
    "                tot += n - a\n",
    "            else:\n",
    "                if b > a:\n",
    "                    tot += b - a\n",
    "\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        nums = [float('inf')] + nums + [float('inf')]\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        right_stack = [0] * n\n",
    "        left_stack = [0] * n\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] >= nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                right_stack[idx] = i\n",
    "                \n",
    "            stack.append(i)\n",
    "            \n",
    "        stack = []\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                left_stack[idx] = i\n",
    "                \n",
    "            stack.append(i)\n",
    "            \n",
    "        res = 0\n",
    "        pre_max = -1\n",
    "\n",
    "        for i in range(1,n-1):\n",
    "            \n",
    "            if nums[i] >= left and nums[i] <= right:\n",
    "                res += (right_stack[i]-i) * (i-left_stack[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        allsame=True\n",
    "        n=len(nums)\n",
    "        for num in nums:\n",
    "            if not num==nums[0]:\n",
    "                allsame=False\n",
    "        if allsame:\n",
    "            return (n+1)*n//2\n",
    "        rbound=[0 for i in range(n)]\n",
    "        lbound=[0 for i in range(n)]\n",
    "        stack=[]\n",
    "        for i in range(n):\n",
    "            while len(stack)>0 and stack[-1][0]<=nums[i]:\n",
    "                rbound[stack[-1][1]]=i-stack[-1][1]-1\n",
    "                stack=stack[:-1]\n",
    "            stack.append([nums[i],i])\n",
    "        while len(stack)>0:\n",
    "            rbound[stack[-1][1]]=n-stack[-1][1]-1\n",
    "            stack=stack[:-1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while len(stack)>0 and stack[-1][0]<nums[i]:\n",
    "                lbound[stack[-1][1]]=stack[-1][1]-i-1\n",
    "                stack=stack[:-1]\n",
    "            stack.append([nums[i],i])\n",
    "        while len(stack)>0:\n",
    "            lbound[stack[-1][1]]=stack[-1][1]\n",
    "            stack=stack[:-1]\n",
    "        ans=0\n",
    "        #print(lbound,rbound)\n",
    "        for i in range(n):\n",
    "            if nums[i]>=left and nums[i]<=right:\n",
    "                ans+=(lbound[i]+1)*(rbound[i]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        nums = [float('inf')] + nums + [float('inf')]\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        right_stack = [0] * n\n",
    "        left_stack = [0] * n\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] >= nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                right_stack[idx] = i\n",
    "                \n",
    "            stack.append(i)\n",
    "            \n",
    "        stack = []\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                left_stack[idx] = i\n",
    "                \n",
    "            stack.append(i)\n",
    "            \n",
    "        res = 0\n",
    "        pre_max = -1\n",
    "\n",
    "        for i in range(1,n-1):\n",
    "            \n",
    "            if nums[i] >= left and nums[i] <= right:\n",
    "                res += (right_stack[i]-i) * (i-left_stack[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left_: int, right_: int) -> int:\n",
    "       # 单调栈\n",
    "        n = len(nums)\n",
    "        # 左边比自己大的最近的位置\n",
    "        left, st = [-1] * n, []\n",
    "        for i, v in enumerate(nums):\n",
    "            while st and nums[st[-1]] < v: st.pop()\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        # 右边比自己大于等于的最近的位置\n",
    "        right, st = [n] * n, []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while st and nums[st[-1]] <= nums[i]: st.pop()\n",
    "            if st: right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        # 当前元素作为最大值的区域\n",
    "        print(left)\n",
    "        print(right)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            l, r = i - left[i], right[i] - i\n",
    "            if left_ <= nums[i] <= right_:\n",
    "                print(nums[i], l, r)\n",
    "                ans += l * r\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        \n",
    "        total = 0\n",
    "        length = len(nums)\n",
    "        left_max_idx = [0 for i in range(length)]\n",
    "\n",
    "        queue = []\n",
    "        for (i, num) in enumerate(nums):\n",
    "            while queue and num >= queue[-1][1]:\n",
    "                prev_i, prev_num = queue.pop()\n",
    "            left_max_idx[i] = queue[-1][0] + 1 if queue else 0\n",
    "            queue.append((i, num))\n",
    "        \n",
    "        queue = []\n",
    "        for (i, num) in enumerate(nums[::-1]):\n",
    "            i = length - 1 - i\n",
    "            while queue and num > queue[-1][1]:\n",
    "                prev_i, prev_num = queue.pop()\n",
    "            if left <= num <= right:\n",
    "                right_max_idx = queue[-1][0] - 1 if queue else length - 1\n",
    "                total += ((i - left_max_idx[i] + 1) * (right_max_idx - i + 1))\n",
    "            queue.append((i, num))\n",
    "        \n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums); l, r = [-1] * n, [n] * n\n",
    "        ms = []\n",
    "        for i in range(n):\n",
    "            while ms and nums[ms[-1]] <= nums[i]:\n",
    "                r[ms.pop()] = i\n",
    "            ms.append(i)\n",
    "        ms = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while ms and nums[ms[-1]] < nums[i]:\n",
    "                l[ms.pop()] = i\n",
    "            ms.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                x = (r[i] - i) * (i - l[i])\n",
    "                ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        descs = []\n",
    "        lrange = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            while descs and nums[descs[-1]] <= nums[i]: #相等的向左延伸\n",
    "                descs.pop()\n",
    "            if descs:\n",
    "                lrange.append(descs[-1])\n",
    "            else:\n",
    "                lrange.append(-1)\n",
    "            descs.append(i)\n",
    "\n",
    "        descs = []\n",
    "        rrange = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            while descs and nums[descs[-1]] < nums[i]: #相等的不向右延伸\n",
    "                descs.pop()\n",
    "            if descs:\n",
    "                rrange.append(descs[-1])\n",
    "            else:\n",
    "                rrange.append(len(nums))\n",
    "            descs.append(i)\n",
    "        rrange = rrange[::-1]\n",
    "\n",
    "        # print(lrange, rrange)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < left or nums[i] > right:\n",
    "                continue\n",
    "            # print(i, nums[i], rrange[i], lrange[i], rrange[i] - lrange[i] - 1)\n",
    "            ans += (rrange[i] - i) * (i - lrange[i])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        #求max不超过threshold的子数组个数\n",
    "        def sliding_window(nums, threshold):\n",
    "            heap = []\n",
    "            cnt = defaultdict(int)\n",
    "            res = 0\n",
    "            l, r = 0, 0\n",
    "            while r < len(nums):\n",
    "                cnt[nums[r]] += 1\n",
    "                heapq.heappush(heap, -nums[r])\n",
    "                #堆+字典记数，维护区间内的序和最大值\n",
    "                while l < r and ( -heap[0] > threshold):\n",
    "                    cnt[nums[l]] -= 1\n",
    "                    while heap and cnt[-heap[0]] <= 0:\n",
    "                        heapq.heappop(heap)\n",
    "                    l += 1\n",
    "                if heap and (-heap[0] <= threshold):\n",
    "                    #print(nums[l:r+1], r-l+1)\n",
    "                    res += r-l+1\n",
    "                r += 1\n",
    "            return res\n",
    "        #max在[left,right]区间 = max最大为right的 - max最大为left-1的\n",
    "        return sliding_window(nums, right) - sliding_window(nums, left-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        # >right 一定不可以选, <left当存在一个 [left, right] 的数就可以选 ,  [left, right] 任意选\n",
    "        # 枚举每个数作为子数组的最大值, 尽可能向左向右扩展, 使用单调栈预处理数组, 以O(1)时间获取左右第一个大于该数的索引,\n",
    "        # 左右两侧根据乘法原理计数\n",
    "        # l,r两个数组一个严格, 一个不严格可以避免重复计数问题 同 https://leetcode.cn/problems/sum-of-subarray-minimums/\n",
    "        st = []\n",
    "        n = len(nums)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            while st and num > nums[st[-1]]:\n",
    "                r[st.pop()] = i\n",
    "            if st: \n",
    "                l[i] = st[-1]\n",
    "            st.append(i)\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if left <= num <= right: # 枚举每个数作为子数组的最大值, 尽可能向左向右扩展, 最大值必须在[left, right]内\n",
    "                res += (r[i] - i) * (i - l[i]) # [i, r[i]) 以及 (l[i] ,i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        S = [0] * (len(nums)+1)\n",
    "        pos = [0] * (len(nums)+1)\n",
    "        count = [0] * (len(nums)+1)\n",
    "        index = -1\n",
    "        S[index] = 1000000001\n",
    "        pos[index] = index\n",
    "        for i in range(len(nums)):\n",
    "            item = nums[i]\n",
    "            while S[index] < item:\n",
    "                index -= 1\n",
    "            temp = pos[index]\n",
    "            index += 1\n",
    "            S[index] = item\n",
    "            pos[index] = i\n",
    "\n",
    "            if left <= item <= right:\n",
    "                count[i] = count[temp] + i - temp\n",
    "            elif item < left:\n",
    "                count[i] = count[i-1]\n",
    "        return sum(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1]*n\n",
    "        r = [n]*n\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and nums[i] > nums[mono_stack[-1]]:\n",
    "                mono_stack.pop()\n",
    "            if mono_stack: l[i] = mono_stack[-1]\n",
    "            mono_stack.append(i)\n",
    "\n",
    "        mono_stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while mono_stack and nums[i] >= nums[mono_stack[-1]]:\n",
    "                mono_stack.pop()\n",
    "            if mono_stack: r[i] = mono_stack[-1]\n",
    "            mono_stack.append(i)\n",
    "        return sum([(i-l[i])*(r[i]-i) for i in range(n) if left<=nums[i]<=right])\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                l[i] = i - stack[-1]\n",
    "            else:\n",
    "                l[i] = i + 1\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[i] >= nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                r[i] = stack[-1] - i\n",
    "            else:\n",
    "                r[i] = n - i\n",
    "            stack.append(i)\n",
    "            \n",
    "        ans = 0\n",
    "        # print(l, r)\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += l[i] * r[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        L = [-1] * n\n",
    "        R = [n] * n\n",
    "        res = 0\n",
    "\n",
    "        stack = []\n",
    "        # decreasing \n",
    "        # idx\n",
    "\n",
    "\n",
    "        for i, val in enumerate(nums):\n",
    "            while stack and val > nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                L[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            val = nums[i]\n",
    "            while stack and val >= nums[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                R[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i, (x, l, r) in enumerate(zip(nums, L, R)):\n",
    "            if left <= x <= right:\n",
    "                res += (i - l) * (r - i)\n",
    "        return res\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        lmin = [-1] * n\n",
    "        rmin = [n] * n\n",
    "\n",
    "        stk = []\n",
    "        for i in range(n):\n",
    "            while stk and nums[stk[-1]] < nums[i]:\n",
    "                rmin[stk.pop()] = i \n",
    "            stk.append(i) \n",
    "        \n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] <= nums[i]:\n",
    "                lmin[stk.pop()] = i \n",
    "            stk.append(i) \n",
    "\n",
    "        res = 0 \n",
    "        for i in range(n):\n",
    "            if nums[i] >= left and nums[i] <= right:\n",
    "                res += (i - lmin[i]) * (rmin[i] - i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        '''\n",
    "        对于某个在[left, right]的数x, 需要x作为子数组的最大值\n",
    "        因此可以用单调栈来寻找x右侧比x大的数\n",
    "\n",
    "        为了方便, 可以假设-1的位置上有个inf\n",
    "        '''\n",
    "        \n",
    "        st = [-1, 0] # 单调递减的栈\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            while len(st) >= 2 and nums[i] > nums[st[-1]]:\n",
    "                if left <= nums[st[-1]] <= right:\n",
    "                    # st[-2]是左侧最近的比st[-1]大的数, i是右侧\n",
    "                    ans += (i-st[-1]) * (st[-1] - st[-2]) # 将做右侧可以选择的区间进行组合\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "\n",
    "        # 对于某些x, 他的右边没有比他大的数, 可以假设在n的位置上有个inf\n",
    "        while len(st) >= 2:\n",
    "            if left <= nums[st[-1]] <= right:\n",
    "                ans += (n-st[-1]) * (st[-1] - st[-2])\n",
    "            st.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        # [] * [] * * [] .... \n",
    "        # 有一些max会超出right] 显然tm会把array分成几段，那些max不能在任何subarray中\n",
    "        # 但又要求 subarray 的max要大于 left，例如\n",
    "        # 113 [2,4] 只有包含3的subarray满足条件 11 单独不行\n",
    "        # 所以我们考虑 subarray\n",
    "        # [ & & ] * [ & ] * []\n",
    "        # & 为正好处于[left,right]的元素，* 为超界\n",
    "        # 只考虑 & 所在的subarray的全部组合\n",
    "        \n",
    "        # 如果考虑&对应的所有subarray\n",
    "        # 不如考虑以 & 为 max 的 subarray 的全部数量 -- 贡献法\n",
    "        # 这也就绕开了 * \n",
    "        # 快速计算 需要知道 & 左侧右侧最近的一个他大的人 - 单调栈\n",
    "        n = len(nums)\n",
    "        leftG = [-1]*n \n",
    "        rightG = [n]*n\n",
    "        stack = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while len(stack) > 0 and nums[stack[-1]] <= x: # 对于x右侧的人，会只看到x\n",
    "                # 对于弹出去的人，x是第一个让他们弹出去的人，即为rightMax\n",
    "                d = stack.pop(-1)\n",
    "                rightG[d] = i\n",
    "            # 对于x他的左边第一个比他大的人 就是栈下面一个\n",
    "            leftG[i] = stack[-1] if len(stack)>0 else -1\n",
    "            stack.append(i)\n",
    "        # 结束后栈非空 他们的rightG都是n\n",
    "        for k in stack:\n",
    "            rightG[k] = n\n",
    "\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if left <= x and x <= right:\n",
    "                # 以x为max的最长subarray\n",
    "                # [leftG[x]+1, x, rightG[x]-1] \n",
    "                res += (i-leftG[i])*(rightG[i]-i)\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n=len(nums)\n",
    "        l=[-1]*n\n",
    "        r=[n]*n\n",
    "        st=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and nums[i]>nums[st[-1]]:\n",
    "                l[st.pop()]=i\n",
    "            st.append(i)\n",
    "        st=[]\n",
    "        for i in range(n):\n",
    "            while st and nums[i]>=nums[st[-1]]:\n",
    "                r[st.pop()]=i\n",
    "            st.append(i)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if left<=nums[i]<=right:\n",
    "                res+=(i-l[i])*(r[i]-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "\n",
    "        nums = [float('inf')] + nums + [float('inf')]\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and nums[i] > nums[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                \n",
    "                if nums[idx] >= left and nums[idx] <= right:\n",
    "                    cur1 = idx - stack[-1]\n",
    "                    cur2 = i - idx\n",
    "                    \n",
    "                    res += cur1 * cur2\n",
    "                    \n",
    "            stack.append(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, arr: List[int], l1: int, r1: int) -> int:\n",
    "        n = len(arr)\n",
    "        left = [-1] * n\n",
    "        # find bigger val than cur val\n",
    "        right = [n] * n\n",
    "        # find bigger or equal than cur val\n",
    "        stack = []\n",
    "        for i, num in enumerate(arr):\n",
    "            while stack and num >= arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "            \n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[i] > arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        res = 0\n",
    "        for i, (x, l, r) in enumerate(zip(arr, left, right)):\n",
    "            if l1 <= x <= r1:\n",
    "                res += (i - l) * (r - i) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1 for _ in range(n)]\n",
    "        r = [n for _ in range(n)]\n",
    "\n",
    "        stk = []\n",
    "        for i, num in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] < num:\n",
    "                r[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            while stk and nums[stk[-1]] <= num:\n",
    "                l[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] >= left and nums[i] <= right:\n",
    "                res += (i - l[i]) * (r[i] - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [n] * n, [-1] * n\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            while q and nums[q[-1]] <= nums[i]:\n",
    "                l[q.pop()] = i\n",
    "            q.append(i)\n",
    "        q = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while q and nums[q[-1]] < nums[i]:\n",
    "                r[q.pop()] = i\n",
    "            q.append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                res += (l[i] - i) * (i - r[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        # if cur_num < left || cur_num > right\n",
    "        n, ans = len(nums), 0\n",
    "        L, R = [0] * n, [0] * n\n",
    "        s1, s2 = [], []\n",
    "\n",
    "        for i in range(n):\n",
    "            while s1 and nums[s1[-1]] <= nums[i]:\n",
    "                s1.pop() \n",
    "            L[i] = s1[-1] + 1 if s1 else 0\n",
    "            s1.append(i)\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s2 and nums[s2[-1]] < nums[i]:\n",
    "                s2.pop()\n",
    "            R[i] = s2[-1] - 1 if s2 else n - 1\n",
    "            s2.append(i)\n",
    "    \n",
    "        for i in range(n):\n",
    "            if nums[i] < left or nums[i] > right:\n",
    "                continue\n",
    "            else:\n",
    "                # 当前数字作为最大值落在 [left, right] 范围内\n",
    "\n",
    "                # 左侧数字不能大于当前(小,等于可以)\n",
    "                ans += (i - L[i] + 1) * (R[i] - i + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        left_bounds = [-1] * n\n",
    "        right_bounds = [n] * n\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and nums[mono_stack[-1]] <= nums[i]:\n",
    "                right_bounds[mono_stack.pop(-1)] = i\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        mono_stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while mono_stack and nums[mono_stack[-1]] < nums[i]:\n",
    "                left_bounds[mono_stack.pop(-1)] = i\n",
    "            mono_stack.append(i)\n",
    "        #print('left_bounds:', str(left_bounds))\n",
    "        #print('right_bounds:', str(right_bounds))\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                ans += (i - left_bounds[i]) * (right_bounds[i] - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1]*n\n",
    "        r = [n]*n\n",
    "        mystc = [0]\n",
    "        for ii in range(1,n):\n",
    "            while mystc and nums[ii]>=nums[mystc[-1]]:\n",
    "                mystc.pop()\n",
    "            if mystc:\n",
    "                l[ii] = mystc[-1]\n",
    "            mystc.append(ii)\n",
    "        mystc = [n-1]\n",
    "        for ii in range(n-2,-1,-1):\n",
    "            while mystc and nums[ii]>nums[mystc[-1]]:\n",
    "                mystc.pop()\n",
    "            if mystc:\n",
    "                r[ii] = mystc[-1]\n",
    "            mystc.append(ii)\n",
    "        res = 0\n",
    "        for ii in range(n):\n",
    "            if nums[ii]>=left and nums[ii]<=right:\n",
    "                li = l[ii]\n",
    "                ri = r[ii]\n",
    "                ll = ii-li\n",
    "                rl = ri-ii\n",
    "                res+=ll*rl\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        n=len(nums)\n",
    "        l=[-1]*n\n",
    "        r=[n]*n  \n",
    "        d=[]\n",
    "        for i in range(n):\n",
    "            while d and nums[d[-1]]<nums[i]:\n",
    "                r[d.pop()]=i\n",
    "            d.append(i)\n",
    "        d.clear()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while d and nums[d[-1]]<=nums[i]:\n",
    "                l[d.pop()]=i\n",
    "            d.append(i)\n",
    "        ans=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x<left or x>right:\n",
    "                continue\n",
    "            ans+=(i-l[i])*(r[i]-i)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        def f(nums, right, op):\n",
    "            n = len(nums)\n",
    "            record = []\n",
    "            for i in range(n):\n",
    "                if op == 1:\n",
    "                    if nums[i] > right:\n",
    "                        record.append(i)\n",
    "                if op == 0:\n",
    "                    if nums[i] >= right:\n",
    "                        record.append(i)\n",
    "            res = 0\n",
    "            record = [-1] + record + [n]\n",
    "            for i in range(0, len(record) - 1):\n",
    "                res += round((record[i + 1] - record[i] - 1) * (record[i + 1] - record[i])/2)\n",
    "            return res\n",
    "        return f(nums, right, 1) - f(nums, left, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        n = len(nums)\n",
    "        rb = [n] * n    # rb[i] = j 表示 nums[j] 是 nums[i] 右侧第一个比 nums[i] 大的数\n",
    "        stack = []      # stack 维持非严格降序索引\n",
    "        for j in range(n):\n",
    "            while stack and nums[stack[-1]] < nums[j]:\n",
    "                rb[stack.pop()] = j\n",
    "            stack.append(j)\n",
    "        lb = [-1] * n\n",
    "        stack = []\n",
    "        for j in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] <= nums[j]:\n",
    "                lb[stack.pop()] = j\n",
    "            stack.append(j)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if left <= nums[i] <= right:\n",
    "                res += (i - lb[i]) * (rb[i] - i)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayBoundedMax(self, nums: List[int], l: int, r: int) -> int:\n",
    "        '''\n",
    "        好难好难\n",
    "        子问题\n",
    "        看错题目了。。。\n",
    "\n",
    "        '''\n",
    "        st=[-1]\n",
    "        n=len(nums)\n",
    "        right=[n]*n\n",
    "        left=[-1]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            while len(st)>1 and nums[st[-1]]<x:\n",
    "                y=st.pop()\n",
    "                right[y]=i\n",
    "            left[i]=st[-1] \n",
    "            st.append(i)\n",
    "        ans=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if l<=x<=r :ans+=(right[i]-i)*(i-left[i])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
